package service.QuickSort;

import java.util.List;

import model.SparePart;

/**
 * 
 * @author Csaba Tarkanyi
 * 
 */
public class QuickSort {

	/**
	 * QuickSorting in a List of SpareParts..
	 * 
	 * @param list -
	 *            List where the method is sorting.
	 * 
	 * @author Csaba Tarkanyi
	 */
	public void quicksort(List<SparePart> list) {
		quicksortRec(list, 0, list.size() - 1);
	}

	/**
	 * Sorting a List by splitting it into two smaller Lists. -> making smaller
	 * problem from the big problem and solves them individually.
	 * 
	 * @param list -
	 *            List of SpareParts.
	 * @param low -
	 *            The start index in the sorting area.
	 * @param high -
	 *            The end index in the sorting area.
	 * 
	 * @author Csaba Tarkanyi
	 */
	private void quicksortRec(List<SparePart> list, int low, int high) {
		if (low < high) {
			int p = partition(list, low, high);
			quicksortRec(list, low, p - 1);
			quicksortRec(list, p + 1, high);
		}
	}

	/**
	 * Goes through the List and sorting the element by using swap.
	 * 
	 * @param list -
	 *            List of SpareParts.
	 * @param low -
	 *            The start index in the sorting area.
	 * @param high -
	 *            The end index in the sorting area.
	 * @return to an Integer which was the last index after sorting.
	 * 
	 * @author Csaba Tarkanyi
	 */
	private int partition(List<SparePart> list, int low, int high) {
		SparePart e = list.get(low);// Always the first element in the List (on
		// index "low").
		int i = low + 1;// Now: the second element in the List.
		int j = high;// Now: the last element in the List
		while (i <= j) {
			/*
			 * If the SparePart on index "low" is the same as the SparePart on
			 * index "i" or it is "smaller" than the SparePart on index "i" ->
			 * increase the "i" by one so the program can go forward to check
			 * the next SparePart.
			 */
			if (list.get(i).compareTo(e) == 0 || list.get(i).compareTo(e) < 0)
				i++;
			/*
			 * If the SParePart on index "j/high" in the List is bigger than the
			 * SparePart on index "low" than decrease the "j" by one, so the
			 * program can checks the SparePart before the SparePart on index
			 * "j".
			 */
			else if (list.get(j).compareTo(e) > 0)
				j--;
			/*
			 * In any other case swaps the SpareParts on index "i" and "j" and
			 * increase the "i" by one and decrease the "j" by one.
			 */
			else {
				swap(list, i, j);
				i++;
				j--;
			}
		}
		/*
		 * If there is no more element in the List to check -> swaps the
		 * SparePart on index "low" with the SparePart on index "j" and returns
		 * "j".
		 */
		swap(list, low, j);
		return j;
	}

	/**
	 * Swaps SparePart index "i" with SparePart index "j" in the List.
	 * 
	 * @author Csaba Tarkanyi
	 */
	private void swap(List<SparePart> list, int i, int j) {
		SparePart temp = list.get(i);// temp SparePart on index "i".
		list.set(i, list.get(j)); // Replaces SparePart on index "i" with
		// SparePart on index "j".
		list.set(j, temp);// Puts the temp SparePart to SparePart on index
		// "j".
	}
}